#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0017.py
@time: 2021/9/14 15:42
@desc:
'''
class Solution:
    def maxProfit(self, prices: list) -> int:
        if len(prices)==0:
            return 0
        dp = [0]*len(prices)
        for i in range(1, len(prices)):
            # 计算出(0,i)的最大利润
            min_idx = 0
            min_p = max(prices[:i+1])
            # 找出最小值
            for j in range(i):
                if prices[j]<min_p:
                    min_p = prices[j]
                    min_idx = j
            # 从最小值后面找出最大值
            max_idx = 0
            max_p = -1
            for k in range(min_idx, i+1):
                if prices[k]>max_p:
                    max_idx = k
                    max_p = prices[k]
            cur = max_p - min_p
            dp[i] = max(dp[i-1], cur)

        return dp[-1]

if __name__ == '__main__':
    sl = Solution()
    inp = [1,2]
    r = sl.maxProfit(inp)
    print(r)